package com.lihepeng.leecode.linkedList;

import org.junit.Test;

/**
 * 链表相交
 * 给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author lihepeng
 */


public class Solution0207 {
    /**
     * 两个指针 循环判断是不是相等
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode n1 = headA;
        ListNode n2 = headB;
        while (n1 != n2) {
            n1 = n1 == null ? headB : n1.next;
            n2 = n2 == null ? headA : n2.next;
        }

        return n1;

    }

    @Test
    public void runTest() {
        ListNode headA = new ListNode(1);
        ListNode head2 = new ListNode(2);
        ListNode head3 = new ListNode(3);
        ListNode head4 = new ListNode(4);
        ListNode head5 = new ListNode(5);
        ListNode headB = new ListNode(10);
        headA.next = head2;
        head2.next = head3;
        headB.next = head3;
        head3.next = head4;
        head4.next = head5;

        ListNode intersectionNode = this.getIntersectionNode(headA, headB);
        System.out.println(intersectionNode);
    }

}
